//两字符串多为二维dp
//每次操作可以更换t中的一个字符
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int N = 2e5 + 10;
#define INF 0x3f3f3f3f;
typedef long long int ll;
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//----------------------------------------------------------------------------//
int f[1010][1010];//S串前i个字符中包含T的前j个字符的最小操作数
int main()
{
    close();
    string s, t;
    cin >> s >> t;
    s = ' ' + s;
    t = ' ' + t;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1; i < s.size(); i++) //先枚举s的(长的)
    {
        f[i][0] = 0; //s的前i个字符串中包含t的前0个字符串的最小操作数为0
        for(int j = 1; j < t.size(); j++)
        {
            f[i][j] = f[i - 1][j];//当s[i]不选,满足前i-1个 能拿到 前j个的子字符串的情况
            if(s[i] == t[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);//s前i-1中能拿到s的前j-1个的情况
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);//s[i]!=t[j]
        }
    }
    cout << f[s.size() - 1][t.size() - 1] << '\n';
    //这里的size是更新后的size比如原来3个字母abc变成  空格abc 数目变成4了,结果是abc数目为3,所以要减1
    return 0;
}